
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class bb {
    //自底向上的方法
    public static int bottom(String a,String b,Set<String>seq){
        int m=a.length();
        int n=b.length();
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){
                if(i==0||j==0){
                    dp[i][j]=0;
                }
                else if(a.charAt(i-1)==b.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        if(dp[m][n]>0)
            backtrack(a,b,m,n,dp,"",seq);
        return dp[m][n];
    }
    public static void backtrack(String x,String y,int i,int j,int[][] dp,String path,Set<String> res){
           if(i==0||j==0){
               if(!path.isEmpty())res.add(path);
               return;
           }
           if(x.charAt(i-1)==y.charAt(j-1)){
               backtrack(x,y,i-1,j-1,dp,x.charAt(i-1)+path,res);
           }
           else{
               if(dp[i-1][j]==dp[i][j])backtrack(x,y,i-1,j,dp,path,res);
               if(dp[i][j-1]==dp[i][j])backtrack(x,y,i,j-1,dp,path,res);
           }
    }
    //自顶向下的方法
    public static int top(int m,int n,int[][] k,String a,String b){
        if(m==0||n==0){
            return 0;
        }
        if(k[m][n]!=-1){
            return k[m][n];
        }
        if(a.charAt(m-1)==b.charAt(n-1)){
            k[m][n]=top(m-1,n-1,k,a,b)+1;
        }
        else{
            k[m][n]=Math.max(top(m-1,n,k,a,b),top(m,n-1,k,a,b));
        }
        return k[m][n];
    }
    private static void backtrackTopDown(String X, String Y, int i, int j, int[][] memo,
                                         StringBuilder current, Set<String> sequences) {
        if (i == 0 || j == 0) {
            sequences.add(current.reverse().toString());
            current.reverse(); // 恢复原状以便后续回溯
            return;
        }

        if (X.charAt(i - 1) == Y.charAt(j - 1)) {
            current.append(X.charAt(i - 1));
            backtrackTopDown(X, Y, i - 1, j - 1, memo, current, sequences);
            current.deleteCharAt(current.length() - 1);
        } else {
            int left = top(i-1,j,memo,X,Y);
            int up = top(i,j-1,memo,X,Y);

            if (left >= up) {
                backtrackTopDown(X, Y, i - 1, j, memo, current, sequences);
            }
            if (up >= left) {
                backtrackTopDown(X, Y, i, j - 1, memo, current, sequences);
            }
        }
    }
    public static void main(String[] args) {
        String a="ABCBDAB";
        String b="BDCAB";
        int m=a.length();
        int n=b.length();
        int[][] k=new int[m+1][n+1];
        for(int[] row:k){
            Arrays.fill(row,-1);
        }
        int c=top(m,n,k,a,b);
        Set<String> sequences = new HashSet<>();
        backtrackTopDown(a, b, m, n, k, new StringBuilder(), sequences);
        System.out.println(c);
        System.out.println(sequences);
    }
}
